package BFS解决FloodFill算法;

import java.util.LinkedList;
import java.util.Queue;
// bfs ，先规定上下左右向量，然后vis 来 标记该位置是否访问过防止重复
// 进行遍历，当遍历到符合的二维数组位置时，进入bfs，来搜寻以这个位置为起点上下左右，是否符合条件，符合条件的vis进行标记，并添加到队列中，直到队列为空，返回count
public class 寻找最大面积的岛屿 {
    int [] dx =  { 0,0,1,-1};
    int [] dy = {1,-1,0,0};
    boolean [][] vis = new boolean[51][51];
    int m,n;

    int max = 0;
    int count = 0;
    public int maxAreaOfIsland(int[][] grid)
    {
         m = grid.length;
         n = grid[0].length;
         int ret = 0;
        for(int j = 0;j<m;j++)
        {
            for(int k = 0; k<n;k++)
            {
                if(grid[j][k] == 1 && !vis[j][k])
                {
                  ret = Math.max(ret,bfs(grid,j,k));
                }
            }
        }
        return ret;
    }

    public int bfs(int[][]grid,int j,int k ) // 既要标记陆地，又把陆地面积返回
    {

      int count = 0;
      Queue<int []> q = new LinkedList<>();
      q.offer(new int []{j,k});
      count++;

        while(!q.isEmpty())
        {
            int [] tmp = q.poll();
            int a = tmp[0],b = tmp[1];
            for(int i = 0 ; i<4; i++)
            {
                int x = a + dx[i];
                int y = b + dy[i];
                if(x>0 && x<m && y>0 && y<n && grid[x][y] == '1' && !vis[x][y]) // 规范范围，并且！vis[x][y]表示未被访问过
                {
                        vis[x][y] = true;
                        q.offer(new int []{x,y});
                        count++;
                }

            }

        }
        return count;


    }
}
